#pragma once

#include <iostream>
#include <assert.h>
#include <string>
#include <vector>
#include <initializer_list>

using namespace std ;

namespace gojo
{

    // 作业里面的反向迭代器的实现

    template<class Iterator , class Ret , class Ref>
    struct __vector_Reverse_iterator
    {

        public:

            typedef __vector_Reverse_iterator<Iterator , Ret , Ref> Self ;

            Iterator _it ;

            __vector_Reverse_iterator (Iterator it)
                : _it (it)
            {}

            Ret operator * ()
            {

                return *_it ;

            }

            Ret operator ++ ()
            {

                return *(--_it) ;

            }

            Ret operator ++ (int)
            {

                Self tmp (_it) ;

                --_it ;

                return *tmp ;

            }

            Ret* operator + (Ret it)
            {

                return _it - it ;
                
            }


            void operator += (Ret it)
            {

                _it -= it ;

            }

            Ret operator [] (Ret it)
            {

                return *(_it - it) ;

            }

            bool operator == (const Self& it) const
            {

                return _it == it._it ;
            }

            bool operator != (const Self& it) const
            {

                return _it != it._it ;

            }
        
    } ;
    

    // 模板建议声明和定义不要分离到两个文件,否则及其容易出现报错

    template <class T>
    class vector
    {

        public:


        // vector迭代器的实现

            // 针对迭代器的第一种简单实现,利用指针访问和操作数据

            typedef T* iterator ;

            typedef const T* const_iterator ;

            typedef __vector_Reverse_iterator<iterator , T , T*&> Reverse_iterator ;

            typedef __vector_Reverse_iterator<iterator , T , T*&> const_Reverse_iterator ; 

            iterator begin ()
            {

                return _start ;

            }

            iterator end ()
            {

                return _finish ;

            }

            const_iterator begin () const
            {

                return _start ;

            }

            const_iterator end () const
            {

                return _finish ;

            }

            Reverse_iterator rbegin ()
            {

                return Reverse_iterator (_finish - 1) ;

            }

            const_Reverse_iterator rbegin () const
            {

                return const_Reverse_iterator (_finish - 1) ;

            }

            Reverse_iterator rend ()
            {

                return Reverse_iterator (_start - 1) ;

            }

            const_Reverse_iterator rend () const
            {

                return const_Reverse_iterator (_start - 1) ;

            }

        
        // 默认函数

            // vector () {} // 由于显式实现了拷贝构造(也是构造函数),所以编译器就不会默认构造函数了,可以使用这个方式来构造函数,或者使用指令让编译器默认构造函数

            vector () = default ; // 强制编译器默认构造函数

            vector (const vector<T>& v) // 由于vector的使用涉及到了深拷贝的问题,这里使用现代写法来实现资源的拷贝(更简洁)
            {

                reserve (v.size ()) ;

                for (auto& e : v) // 这里减少拷贝次数,所以使用了引用
                {

                    push_back (e) ;

                }

            }

            // 函数模板
            // 任意类型容器迭代器初始化
            // 如果单纯只写iterator的话,只能适配相同的vector的拷贝问题
            
            template<class InputIterator>
            vector (InputIterator first , InputIterator last)
            {

                while (first != last)
                {

                    push_back (*first) ; // 涉及深拷贝

                    ++first ;

                }

            }

            // 这里的初始化函数有bug,需要运用最新的c20特性
            // 由于这里比较复杂,所以先简单实现两个函数重载的初始化(两个函数的功能相同)

            vector (int n , T val = T ())
            {

                resize (n , val) ;

            }

            vector (size_t n , T val = T ())
            {

                resize (n , val) ;

            }

            // 使用initializer_list类来初始化

            vector (initializer_list<T> il)
            {

                reserve (il.size ()) ;

                for (auto& e : il)
                {

                    push_back (e) ;

                }

            }

            ~vector ()
            {

                if (_start)
                {

                    delete [] _start ;

                    _start = _finish = _endofstorage = nullptr ;

                }

                // cout << "~vector ()" << endl ;

            }

        
        // 增

            void reserve (size_t n)
            {

                if (n > capacity ())
                {

                    size_t old_size = size () ;

                    T* tmp = new T [n] ;

                    // 拷贝旧数据到新空间

                    if (_start)
                    {

                        // memcpy (tmp , _start , sizeof (T) * old_size) ; 这样子拷贝的成本会增加,使用循环的优化会好一些

                        for (size_t i = 0 ; i < old_size ; i++)
                        {

                            tmp [i] = _start [i] ;

                        }

                        // 将源数据删除

                        delete [] _start ;

                    }

                    _start = tmp ;

                    _finish = _start + old_size ;

                    _endofstorage = _start + n ;

                }

                // 如果是缩容,由于没有规定,所以一律不做处理

            }

            void resize (size_t n , T val = T ()) // 利用了内置类型的匿名构造,在cpp里面内置类型都有相对应的类
            {

                if (n > capacity ())
                {

                    reserve (n) ;

                    while (_finish != _start + n)
                    {

                        *_finish = val ;

                        ++_finish ;

                    }

                }

                else
                {

                    _finish = _start + n ;

                }
                
            }

            void push_back (const T& x)
            {

                if (_finish == _endofstorage)
                {

                    reserve (capacity () == 0 ? 4 : capacity () * 2) ;

                }

                *_finish = x ;

                ++_finish ;

            }

            iterator insert (iterator pos , const T& x)
            {

                assert (pos >= _start && pos <= _finish) ;

                // 如果容量不够,先扩容

                if (_finish == _endofstorage)
                {

                    size_t len = pos - _start ;

                    reserve (capacity () == 0 ? 4 : 2 * capacity ()) ;

                    // 更新pos

                    pos = _start + len ;
                    
                }

                iterator end = _finish - 1 ; // 不是size_t,不用考虑溢出问题

                while (end >= pos)
                {

                    *(end + 1) = *end ;

                    --end ;

                }

                *pos = x ;

                ++_finish ;

                return pos ;

            }


        // 删

            void pop_back ()
            {

                assert (!empty ()) ;

                --_finish ;

            }

            iterator erase (iterator pos)
            {

                assert (pos >= _start && pos <= _finish) ;

                iterator it = pos + 1 ;

                // 挪动数据

                while (it != _finish)
                {

                    *(it - 1) = *it ;

                    ++it ;

                }

                --_finish ;

                return pos ;

            }

            void clear ()
            {

                _finish = _start ; // 这里注意,不要把_finish赋值给_start,不然会报错

            }

        // 改

            void swap (vector<T>& v)
            {

                std::swap (_start , v._start) ;

                std::swap (_finish , v._finish) ;

                std::swap (_endofstorage , v._endofstorage) ;
                
            }

            // 现代写法
            vector<T>& operator = (vector<T> v)
            {

                swap (v) ;

                return *this ;

            }

            T& operator [] (size_t i)
            {

                assert (i < size ()) ;

                return _start [i] ;

            }

            T& operator [] (size_t i) const
            {

                assert (i < size ()) ;

                return _start [i] ;

            }
            

        // 查

            size_t capacity () const
            {

                return _endofstorage - _start ; // 开区间减闭区间

            }

            size_t size () const
            {

                return _finish - _start ; // 开区间减闭区间
            }

            bool empty () const
            {

                return _start == _endofstorage ;

            }

        private:

            iterator _start = nullptr ;
            
            iterator _finish = nullptr ;

            iterator _endofstorage = nullptr ;

    } ;

    // 这里使用了泛型 函数编程

    template<class Container>
    void Print (const Container& con)
    {

        for (auto e : con) // 迭代器
        {

            cout << e << " " ;

        }

        cout << endl ;
    }

}